package com.hdu.point_offer;

public class lcr129 {
    class Solution {
        boolean[][] used;
        int[][] directions = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        public boolean wordPuzzle(char[][] grid, String target) {
            used = new boolean[grid.length][grid[0].length];
            int m = grid.length;
            int n = grid[0].length;
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (grid[i][j] == target.charAt(0) && f(grid, i, j, target, 0))
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        boolean f(char[][] grid, int row, int col, String target, int index)
        {
            if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length)
            {
                return false;
            }
            if (used[row][col])
            {
                return false;
            }
            if (grid[row][col] != target.charAt(index))
            {
                return false;
            }
            if (index == target.length() - 1)
            {
                return true;
            }
            used[row][col] = true;
            boolean flag = false;
            for (int[] direction : directions)
            {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                flag = flag || f(grid, newRow, newCol, target, index + 1);
                if (flag)
                {
                    return true;
                }
            }
            used[row][col] = false;
            return flag;
        }
    }
}
